#include "junix.h"
#include <boost/bind.hpp>
using namespace std;

class heap {
	public:
		heap(vector<int>& v, int size) 
			:V(v), N(size)
		{ }

		void fix_down(int i) {
			if (i<0 || i>=N)
				return ;

			int l = 2*i+2;
			int r = l+1;
			int min = i;

			if (l<N && V[l]<V[i])
			   	min = l;
			if (r<N && V[r]<V[min]) 
				min = r;

			if (min!=i) {
				swap(V[min], V[i]);
				fix_down(min);
			}
		}

		void heap_sort() {
			for (int i=N%2+1; i>=0; i--) {
				fix_down(i);
			}

			int t = N;
			while (N>0) {
				swap(V[0], V[N-1]);
				--N;
				fix_down(0);
			}

			N=t;
		}

		int N;
		vector<int> V;
};

int main()
{
	using boost::bind;
	srand(time(0));
	vector<int> V(20);
	generate( V.begin(), V.end(),
			  bind(modulus<int>(), bind(rand), 20));

	heap H(V,V.size());
	H.heap_sort();

	copy(H.V.begin(), H.V.end(),
			ostream_iterator<int>(cout," "));
	cout<<endl;
}
